package at.fhooe.mc.task01;

/**
 * @author Felix Gruber <br>
 *         S1310237015 <br>
 *         Mobile Computing <br>
 *         FH Hagenberg
 */
public class Quicksort<T> implements Sorter<T> {
	public void sort(Comparable<T>[] a) {
		qsort(a, 0, a.length - 1);
	}

	private void qsort(Comparable<T>[] a, int from, int to) {
		Comparable<T> x;
		if (from < to) {
			x = a[(from + to) / 2];
			int i = from;
			int j = to;
			do {
				while (a[i].compareTo((T) x) < 0 && i < to) {
					i++;
				}
				while (x.compareTo((T) a[j]) < 0 && j > from) {
					j--;
				}
				if (i <= j) {
					Comparable<T> temp = a[j];
					a[j] = a[i];
					a[i] = temp;
					i++;
					j--;
				}
			} while (i <= j);
			qsort(a, from, j);
			qsort(a, i, to);
		}
	}
}